// 2025/11/16
// 最长回文子串

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for(int i = 0; i < n; i++)
            dp[i][i] = true;
        int pos = 0, len = 1;
        for(int i = n - 2; i >= 0; i--)
        {
            for(int j = i + 1; j < n; j++)
            {
                if(s[i] == s[j] && (dp[i + 1][j - 1] || j == i + 1))
                {
                    dp[i][j] = true;
                    if(j - i + 1 > len)
                    {
                        pos = i;
                        len = j - i + 1;
                    }
                }
            }
        }
        return s.substr(pos, len);
    }
};